package com.leetcodehot.problems;

public class problems42 {
    //空间复杂度为O(n)的做法
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
    //空间复杂度为O(1)的做法如下
    /**
     * public int trap(int[] height) {
     *         int ans = 0;
     *         int left = 0;
     *         int right = height.length - 1;
     *         int preMax = 0; // 前缀最大值，随着左指针 left 的移动而更新
     *         int sufMax = 0; // 后缀最大值，随着右指针 right 的移动而更新
     *         while (left < right) {
     *             preMax = Math.max(preMax, height[left]);
     *             sufMax = Math.max(sufMax, height[right]);
     *             ans += preMax < sufMax ? preMax - height[left++] : sufMax - height[right--];
     *         }
     *         return ans;
     *     }
     *
     */
}
